Algebraic attacks on BitCoin

% Remco Bloemen % 2015-08-26

cnfgen

results

generating-cnf

BitCoin proof of work

  1. Block header

    Size Field


4 bytes Version 32 bytes hashPrevBlock 32 bytes hashMerkleRoot 4 bytes Time 4 bytes Difficulty 4 bytes Nonce

struct block_header {
	unsigned int    version;         //  32 bit
	unsigned char   prev_block[32];  // 256 bit
	unsigned char   merkle_root[32]; // 256 bit
	unsigned int    timestamp;       //  32 bit
	unsigned int    bits;            //  32 bit
	unsigned int    nonce;           //  32 bit
};

Whenever Nonce overflows (which it does frequently), the extraNonce portion of the generation transaction is incremented, which changes the Merkle root.

The block hash is

SHA256(SHA256(block_header))

The block header is 640 bits of which the last 32 bit can change.

In SHA256 preprocessing the message is split in two chunks.

First chunk 512 bits containing only fixed content.

Second chunk 128 bits + 1 x one + 319 x zero + 0x0000000000000280.

The nonce are bits 96..127 in the second chunk, mapping to w[3] in sha256.

Result is 256 bit hash.

Second hash only has one chunk: 256 bit hash1 + 1 x one + 191 x zero + 0x0000000000000100

The block header is 640 bits of which the last 32 bit can change.

In SHA256 preprocessing the message is split in two chunks.

First chunk 512 bits containing only fixed content.

Second chunk 128 bits + 1 x one + 319 x zero + 0x0000000000000280.

The nonce are bits 96..127 in the second chunk, mapping to w[3] in sha256.

Result is 256 bit hash.

Second hash only has one chunk: 256 bit hash1 + 1 x one + 191 x zero + 0x0000000000000100

cnfgen.py

Remco Bloemen
Math & Engineering
https://2π.com